/**
 * @param {number} n
 * @return {number[]}
 */
export var lexicalOrder = function (n) {
  let num = 1
  let ans = []
  for (let i = 0; i < n; i++) {
    ans[i] = num
    if (num * 10 <= n) {
      num *= 10
    } else {
      // 重置到个位开始 299 -> 29 -> 2 -> 3
      while (num % 10 === 9 || num + 1 > n) {
        num = Math.floor(num / 10)
      }
      num++
    }
  }
  return ans
}

/**
 *  深度优先搜索，可以看作是n叉树。
 *        1       |       2      |         3
 * 10     11    12     13  | 20  21  22   23  | 30   31    32   33
 * 100 101 ... 110 111 ... 120 121 ... | 200 201 ... 210 211 ...| ...
 * @param {number} n
 * @return {number[]}
 */
export var lexicalOrder2 = function (n) {
  let ans = []
  const dfs = num => {
    if (num > n) return
    ans.push(num)

    for (let i = 0; i < 10; i++) {
      dfs(num * 10 + i)
    }
  }
  for (let i = 1; i < 10; i++) {
    dfs(i)
  }
  return ans
}
